\subsection{Übungsblatt 5 - Hashfunktionen}
\subsubsection{Übung (i) - Angriffe auf Hashfunktionen}
\paragraph{Aufgabenstellung}  \hfill \\
Benutzerpasswörter werden (idealerweise ;-) nicht im Klartext auf einem System gespeichert. Eine Möglichkeit ist, dass der Server nur Hashwerte der Passwörter kennt und diese beim Login der Clients mit dem Bild des eingegebenen Passworts unter der Hashfunktion $h$ vergleicht. Angenommen, ein Angreifer hat eine Kopie der Passwort-Datei. Mit welchen Angriffen kann er sich für einen legitimen Benutzer ausgeben?  \hfill \\
Im Folgenden werden mögliche Angriffe auf die Hashfunktionen beschrieben. Diese werden unter der Voraussetzung angegriffen, dass kein Salt verwendet wurde.

\begin{enumerate}
	\item Brechen der Einweg-Eigenschaft von $h$ \hfill \\
Hashfunktionen bedienen sich sogenannter Einwegfunktionen, ohne dass bekannt ist, ob es solche Funktionen gibt. Entsprechend existiert die (wenn auch unwahrscheinliche) Möglichkeit, dass der Angreifer die Umkehrfunktion der Einwegfunktion ermittelt. \hfill \\  
Sei $h: x \longrightarrow h(x)$ eine Hashfunktion. Angenommen der Angreifer kann zu einen Hashwert $h(x)$ ein Urbild $y$ berechnen, so dass gilt: $h(y)=h(x)$, aber nicht zwingend $x=y$. Dadurch ist es ihm möglich aus jedem Hashwert $h(x)$ einen $h(x)$ generierenden Wert $y$ zu errechnen. Somit kann er für jeden Hashwert ein gültiges Passwort berechnen. Dadurch ist er in der Lage sich als beliebiger Benutzer auszugeben, da er für jeden Hashwert ein den Hash generierende Eingabe ermitteln kann. Ist der Angreifer in der Lage die Einweg-Eigenschaft zu brechen, so ist auch die schwache und starke Kollisionsresistenz gebrochen.
	\item Brechen der (schwachen) Kollisionsresistenz von $h$ \hfill \\  
	\textbf{Definition schwache Kollisionsresistenz (Buchmann, 2010, S. 194)}	
	\begin{quote}
Die Funktion $h$ heißt schwach kollisionsresistent, wenn es praktisch unmöglich ist, für ein vorgegebenes $x \in D$ eine Kollision $(x, x')$ zu finden.  
	\end{quote}
Zum Brechen der schwachen Kollisionsresistenz von $h$ wird nach einem Eingabewert $x'$ gesucht, welcher durch Anwendung der Hashfunktion $h$ den gleichen Hashwert $H$ ausgibt. Beim Brechen der schwachen Kollsionsresistenz ist der gegebene Hashwert $H$, da er einem konkreten Benutzer zugeordnet werden kann. Daher wird eine Kollision $(x', a)$ gesucht. Gesucht ist $x':h(x')=h(a)$. Kann eine solche Kollision mit vertretbarem Aufwand gefunden werden, so kann der Angreifer sich für diesen Benutzer mit dem Hashwert $H$ durch die  gefundene Kollision Zugriff auf das System erlangen. Ist der Angreifer in der Lage die schwache Kollisionsresistenz zu brechen, so ist auch die starke Kollisionsresistenz gebrochen.
	\item Brechen der starken Kollisionsresistenz von $h$ \hfill \\ 
\textbf{Definition starke Kollisionsresistenz (Buchmann, 2010, S. 194)}
		\begin{quote}
Die Funktion $h$ heißt (stark) kollisionsresistent, wenn es praktisch unmöglich ist, irgendeine Kollision $(x, x')$ zu finden.  
	\end{quote}
Zum Brechen der starken Kollisionsresistenz von $h$ wird nach einem Eingabewert $x'$ gesucht, welcher durch Anwendung der Hashfunktion $h$ den Hashwert $H$ ausgibt, welcher auch von einem beliebigen anderen Eingabewert $x$ generiert wird. Entsprechend haben wir es hierbei mit zwei Variablen zu tun, sodass die Chance auf eine Kollision sich anhand der Geburtstagsattacke ermitteln lässt. Durch das Brechen der starken Kollisionsresistenz wird unter Umständen eine Autorisierung möglich, allerdings nur, wenn die gefundene Kollision in irgendeinem Benutzer auftritt. \hfill \\
Sei $h: x \longrightarrow h(x)$, so ist eine Kollision $(x', x)$ wenn $h(x') = h(x)$ gilt. Wird nun eine Kollision ermittelt, so muss für einen erfolgreichen Login der Hashwert der Kollision einem Benutzer zugeordnet sein. Ist dies nicht der Fall, so ist ein Login nicht möglich.
\end{enumerate}

\paragraph{Verwendung eines sogenannten Salts} \hfill \\ 


Oftmals wird einem Passwort $p$ ein zufälliger Bitstring $s$ (auch Salt genannt) vorangestellt und in der Passwortdatei $h(s \circ p)$ zusammen mit $s$ gespeichert. Was bezweckt man damit? \hfill \\  
Die Verwendung eines solchen Salts bezweckt, dass bei zwei Benutzern mit dem gleichen Passwort nicht der gleiche Hashwert generiert wird. Daher sind Rückschlüsse auf das Passwort der anderen Person nicht möglich, sofern dies der Fall ist. Des Weiteren wird durch die Verwendung eines solchen Salts verhindert, dass ein Angreifer eine Tabelle mit den Werten $(x, h(x))$ einmalig mit beliebten Passwörtern und Wörtern aus dem Wörterbuch vorrechnet und diese Tabelle anschließend als Nachschlagewerk für das dazugehörige Urbild verwendet. Dieser Angriff funktioniert immer noch, jedoch muss für diesen Angriff eine Tabelle mit den Werten $(x, h(s \circ x))$ berechnet werden. Da der Salt zufällig ist, werden mehrere Tabellen benötigt, was den Speicherplatzbedarf für die Vorberechnungen erhöht und den Angriff dadurch unpraktikabel macht.

\paragraph{Exkurs: Einsatz eines Salts} \hfill \\ 
Da jeder Benutzer ein eigenes Passwort besitzt und bei der Benutzererstellung ein eigener zufälligen Salt generiert wurde, hängen die hier verwendeten Variablen $p$ für das Passwort und $s$ für den Salt jeweils von dem User ab. \hfill \\
 Sei \textit{p} ein Passwort, $u$ ein Benutzer und $s$ der Salt, so bildet folgende Funktion den gespeicherten Hashwert $H$ ab:
\[H_u=h(s_u \circ p_u) \]
Eine Benutzerauthentifizierung prüft, ob das eingegebene Passwort $p_u$ in der Verbindung mit dem Salt $s_u$ den Hashwert $H_u$ ergibt.
Unter der Annahme, dass der Angreifer die Passwortdatei bekommen konnte, allerdings keine Änderungen an der Passwortdatei durchführen kann, benötigt er weiterhin für eine korrekte Authentifizierung eine Eingabe, welche den gespeicherten Hashwert aus der Verbindung der Eingabe und des Salts generiert. Möchte nun der Angreifer sich als bestimmter Benutzer ausgeben, so wird ein Angriff auf die schwache Kollisionsresistenz durchgeführt. 
\hfill \\ \hfill \\ Sei $H_u = h(s_u \circ p_u)$ und $H_u = H'_u$, so ist eine Kollision $(s_u \circ p_u, s_u \circ p'_u)$ zu finden, da die Generierung des Hashwertes von dem Salt $s_u$ abhängt und entsprechend gilt:
\[h(s_u \circ p_u)=H_u=H'_u=h(s_u \circ p'_u) \]
Sollte der Angreifer nun eine Kollision ermitteln, ist diese für ihn lediglich wertvoll, wenn der Anfang der ermittelten Kollision dem vorangestellten Bitstring gleicht. Ist dies nicht der Fall, so kann der Angreifer bei der Passworteingabe keinen Wert $p_u$ eingeben, welcher in Verbindung mit dem hinterlegten Salt $s_u$ den Hashwert $H_u$ generiert. Somit ist die Chance eine Kollision zu finden in Abhängigkeit von der Länge des Salts gesunken. Diese Vorgehensweise erhöht die Sicherheit der Authentifizierung indem es die Chance eine geeignete Kollision zu finden erheblich verringert. Sie schützt jedoch nicht vor dem Brechen der Einweg-Eigenschaft von $h$, da durch diese möglicherweise eine entsprechende Lösung gefunden werden kann.

\paragraph{Genügt es, wenn die Ausgaben von $h$ nur 80 Bit lang sind?}
Fehlt noch

\subsubsection{Übung (ii) - Rainbow Tables}
Zur Erstellung dieses Abschnittes wurde als Quelle Wikipedia verwendet, insbesondere der Artikel "`Rainbox Tables"'. Nachdem Wikipedia die Idee der Rainbow-Tables dargestellt hat, wurde die Verfahrensweise aufgegriffen und dargestellt.
\paragraph{Aufgabenstellung} \hfill \\ 
Erklären Sie das Prinzip eines Angriffs mittels Rainbow-Tables.
\paragraph{Anwendungszweck von Rainbow-Tables} \hfill \\ 
Rainbow-Tables werden angewendet um einen effizienten Angriff auf einen gegebenen Hashwert zu ermöglichen. Es ist also eine Angriffsmethode auf das zweite Urbild. Dieser Angriff funktioniert allerdings lediglich bei Hashfunktionen, welche keinen Salt verwenden um ein Passwort zu speichern. Hierbei werden für die Hashfunktion eine Tabelle angelegt, welche nicht alle Elemente beinhaltet um den Speicherplatz zu minimieren, allerdings die Möglichkeit bietet sie zu durchsuchen. Die Tabellen werden nur einmalig erstellt und dienen anschlie\ss end als Nachschlagewerk.
\paragraph{Aufbau von Rainbow-Tables} \hfill \\ 
Rainbow-Tables basieren auf zwei Funktionen: 
\begin{itemize}
\item Der Hashfunktion $h: \{0,1\}^* \rightarrow \{0,1\}^n$ und 
\item der Reduktionsfunktion $r\{0,1\}^n \rightarrow \{0,1\}^n$. 
\end{itemize}
Die Hashfunktion ist hierbei die Funktion, welche zur Passwortgenerierung verwendet wurde. Die Reduktionsfunktion ist eine Funktion, welche aus dem generierten Hashwert einen neuen Wert generiert, welcher die gleiche Länge wie der vorherige Eingabewert hat. Hierbei ist eine gute Reduktionsfunktion eine Funktion, welche keine Kollisionen in dem generierten Wort aus dem Hashwert ermittelt. Bei einer schlechten Reduktionsfunktionen treten innerhalb einer Kette der Rainbow-Table bereits Kollisionen auf. Dies hat zur Folge, dass sich innerhalb einer Kette bereits berechnete Wörter wiederholen. Die Funktion der Reduktionsfunktion ist, dass bei einer Kette mit der Länge $n$ Elemente, jedes Element einen eigenen Wert speichert. Kommen darin Wiederholungen vor, so speichert die Kette weniger als $n$ Hashpärchen, was sie ineffizient werden lässt. \hfill \\ 
Eine generierte Rainbow-Table besteht hierbei lediglich aus dem Startwert (initiales Kennwort) und dem letzten Hashwert der Kette. Zu jeder Rainbow-Table gehört eine gewisse Anzahl an Iterationen, welche festgelegt werden muss. Liegt die Anzahl der Iterationen bei $1$, so ist die Rainbow-Table lediglich eine Hashtabelle mit dem Aufbau $h:x \mapsto h(x)$. Daher werden mehrere Iterationen verwendet. Der daraus resultierende Vorteil wird bei einem Angriff erklärt. \hfill \\ 
Sei $x_i$ eine Zeile der Rainbow-Table und $z_i^j$ alle in der Kette enthaltenen Kennwörter für $0<=j<=m$, $H_m$ die aus den Kennwörtern resultierenden Hashwerte, $x_0$ das Initialkennwort und $m$ die Anzahl der Iterationen, dann wird die Rainbow-Table wie folgt generiert:
\begin{enumerate}
\item Anwenden der Hashfunktion auf das Initialkennwort: $h: x_i \mapsto H_i^0$
\item Anwenden der Reduktionsfunktion auf den Initialhash: $r: H_i^0 \mapsto z_i^1$
\item Anwenden der Hashfunktion auf das generierte Kennwort: $h: z_i^1 \mapsto H_i^1$
\item Anwenden der Reduktionsfunktion auf den generierten Hashwert: $r:H_i^j \mapsto z_i^{j+1}$
\item Durchführung der Schritte 3. und 4. bis die Anzahl der Iterationen $j=m$ erreicht ist.
\item Speichern des Initialkennwortes $x_i$ und des letzten Hashwertes $H_i=H_i^m$ in der Tabelle.
\end{enumerate}
Die Besonderheit besteht hierbei darin, dass bei dem Wissen über die verwendete Hashfunktion und die verwendete Reduktionsfunktion jedes Element der Kette wieder generiert werden kann und somit eine Kette die Anzahl von $m+1$ Kennwort-Hashwert-Paaren enthält.

\paragraph{Angriff mittels Rainbow-Tables} \hfill \\ 
\textit{Quelle: Wikipedia - Artikel Rainbow-Tables}
Bekannt sein nun ein Hashwert $H=h(p)$, welcher aus einer Passwortdatei entnommen wurde, über die bekannt ist, dass sie die Hashfunktion $h$ ohne Verwendung eines Salts zur Passwortgenerierung verwendet. Um einen solchen Angriff ausführen zu können werden folgende Informationen benötigt:
\begin{itemize}
\item Hashwert des Passwortes: $H_0=h(p)$
\item Eine bereits generierte Rainbow-Table: $T$
\item Die Kettenelemente der Rainbow-Table: $t_k \in T:t_k=(x_k, H_k)$
\item Die zur Generierung verwendete Hashfunktion
\item Die zur Generierung der Rainbow-Table verwendete Reduktionsfunktion
\end{itemize}
Gesucht ist das Passwort $p$. Der Angriff auf den Hashwert läuft nun wie folgt ab:
\paragraph{Finden eines übereinstimmenden Hashwertes}
\hfill \\
Die Vorgehensweise wird hier in Pseudocode verdeutlicht. Sobald ein übereinstimmendes Element gefunden wird, ist die nächste Methode anzuwenden.
\begin{enumerate}
\item Setzen der Iterationsvariable: $i:=0$.
\item Prüfen, ob die Iterationsvariable $i<m$, wobei $m$ die Länge der Ketten beschreibt. Ist dies der Fall, so kann das Urbild nicht mittels der Rainbow-Table gefunden werden.
\item Überprüfen, ob es ein Element gibt mit: $t_k:H_k=H_i$
\item Generieren des nächsten Hashwertes: $H_{i+1}=h(r(H_i))$
\item Erhöhen der Iterationsvariable: $i:=i+1$
\item Gehe zu Schritt 2.
\end{enumerate}

\paragraph{Ermitteln eines dazugehörigen Klartextes}
\hfill \\
In der vorhergehenden Methode wurde ein Element $t_k$ ermittelt, bei welchem der gespeicherte Hashwert $H_k$ mit einem aus dem Hashwert $h(p)$ generierten Hashwert $H_i$ übereinstimmt.
\hfill \\
Nun besteht die Wahrscheinlichkeit, dass das verwendete Passwort in der Kette $t_k$ enthalten ist. Entsprechend wird die Kette von $t_k$ wieder generiert und überprüft, ob darin ein Hashwert $H_q$ generiert wurde, welcher den Hashwert $h(p)$ besitzt. Sei nun $H_q=h(p)$, so ist eine Kollision gefunden mit $(x_q, h(p))$. Dadurch wurde das Passwort geknackt und der Angreifer erhält Zugriff auf das System.
\hfill \\
In Pseudocode sieht die Vorgehensweise wie folgt aus:
\begin{enumerate}
\item Setzen der Iterationsvariable: $q:=0$.
\item Anwenden der Hashfunktion auf das erste Element der Kette: $h: x_i \mapsto H_i^0$
\item Wenn $H_i^0=h(p)$, dann Ausgabe von $z_{q+1}$. Ist schon im ersten Versuch eine Übereinstimmung gefunden, so ist $x_i$ das gesuchte Passwort.
\item Erhöhen der Iterationsvariable: $q:=q+1$
\item Berechnen des nächsten Hashwertes: $H_{q+1}=h(r(z_q))$
\item Überprüfen ob $H_i^q=h(p)$. Falls dies der Fall ist, so ist $z_q$ das gesuchte Passwort.
\item Gehe zu Schritt 5.
\end{enumerate}
Sollte nun eine Übereinstimmung der Hashwerte $H_q=h(p)$ ermittelt werden, ist eine Kollision $(z_q, h(p))$ gefunden und der Angreifer kann sich unter der Verwendung von $z_q$ einloggen. Wird keine Kollision gefunden, so ist weiter nach übereinstimmenden Hashwerten zu suchen. (siehe weiter oben)
\hfill \\
Dieses Verfahren funktioniert nicht mit hundertprozentiger Wahrscheinlichkeit. Gründe hierfür sind:\hfill \\
Die Kette besitzt lediglich die vorher festgelegte Länge $m$, sodass die Möglichkeit besteht, dass eine Kollision erst nach Anwendung von mehr als $m$ Anwendungen der Reduktions- und Hashfunktionen gefunden wird. In diesem Fall ist zwar eine Kollision gefunden, allerdings wird das Element $x_i$ möglicherweise aus dem hinterlegten Hash generiert. Dadurch befindet sich das Passwort vor dem Anfang der Kette und es kann kein Passwort gefunden werden, obwohl eine Übereinstimmung gefunden wurde.
\hfill \\
Insgesamt spart die Verwendung von Rainbow-Tables jedoch viel Speicherplatz zulasten von erhöhtem Rechenaufwand bei einem Vergleich mit einer normalen Hashtabelle. Dafür ist jedoch nur eine gewisse Wahrscheinlichkeit einer Kollision anzunehmen, sodass unter Umständen keine Kollision gefunden wird.

\subsubsection{Übung (iii) - Geburtstagsattacke}
\paragraph{Aufgabe}
Gegeben seien drei Hashfunktionen, deren Hashwerte 64, 128 und 160 Bit lang sind. Bestimmen Sie jeweils die Anzahl an Texten,
die Sie zufällig wählen müssen, um mit Wahrscheinlichkeit $\epsilon$ eine Kollision zu erhalten. Betrachten Sie die Fälle 
$\epsilon$ = 1/2 und $\epsilon$ = 1/10. (Hinweis: Abschätzung in Abschnitt 5.3)

\paragraph{Lösung}
Zunächst beschäftigen wir uns mit der Wahrscheinlichkeit 
$\epsilon$ = 1/2. In BUCHMANN Kapitel 12.2 ist eine Formel gegeben, mit deren
Hilfe man die Anzahl an Texten berechnen kann die erzeugt werden müssen um mit einer Wahrscheinlichkeit von $\epsilon$ = 1/2 eine Kollision 
zu erhalten.\\ \\k $\geq$ (1+$\sqrt{1+(8ln2)\left| \Sigma \right|^n})/2$\\
\begin{itemize}
\item k ist die Anzahl der zu erstellenden Dokumente
\item $\left| \Sigma \right|$ ist die Anzahl an Objekten im Alphabet. Da es sich um Bitstrings handelt ist diese 2
\item n ist die Länge des Alphabetes
\end{itemize}
(1+$\sqrt{1+(8ln2)2^{64}}$)/2 $\leq$ 5.057*$10^9$ Dokumente\\
(1+$\sqrt{1+(8ln2)2^{128}}$)/2 $\leq$ 2.172*$10^{19}$ Dokumente\\
(1+$\sqrt{1+(8ln2)2^{160}}$)/2 $\leq$ 1.4234*$10^{24}$ Dokumente\\ \\ \\Um die Wahrscheinlichkeit für $\epsilon$ = 1/10 zu berechnen,
kann man die Gleichung aus BUCHANN Kapitel 5.3 ab folgendem Zwischenschritt:\\\\
q $\leq$ $e^{-k(k-1)/(2n)}$\\\\
durch Umformung und die richtige Wahl der Wahrscheinlichkeit verwenden. Wie das funktioniert wird im folgenden beschrieben.\\ \\
Herauszufinden ist die Wahrscheinlichkeit p, eine Kollision zu erhalten. Um diese Variable zu erhalten ist es einfacher mit dem
Gegenereignis q zu rechnen. Diese berechnet die Wahrscheinlichkeit dafür, keine Kollision zu erhalten. Die Variable k ist die Anzahl an 
Texten die gewählt werden muss. Der erste Schritt besteht darin für q die Wahrscheinlichkeit des Gegenereignisses einzusetzen.
Diese ist:\\\\
q = 1 - 1/10 = 0,9\\\\ 
Als nächstes wird die Gleichung logarithmiert. Dadurch erhält man:\\\\
ln(0,9) $\leq$ -k(k-1)/(2n)\\\\
Nach dem Ausklammern der rechten Seite und der Multiplikation mit 2n sieht die Gleichung wie folgt aus:\\\\
ln(0,9)2n $\leq$ $k-k^2$\\\\
Nun Addieren wir die Gleichung mit $k^2$ und subtrahieren k und erhalten dadurch:\\\\
$k^2$ - k + ln(0,9)2n $\leq$ 0\\\\
Aus dieser quadratischen Gleichung ergibt sich die Lösungsformel:\\\\
(1-$\sqrt{1-8ln(0,9)n}$)/2  $\leq$ (1+$\sqrt{1-8ln(0,9)n}$)/2\\\\
Wenn nun ein\\\\
k $\geq$ (1+$\sqrt{1-8ln(0,9)n})/2$\\\\
gewählt wird, dann wird q kleiner als 0,9 und p damit größer als 0,1. Die Variable n wird dabei durch das Alphabet $\left| \Sigma \right|^n$
ersetzt.\\\\ 
Setzt man die Bitlängen der verschiedenen Hashwerte ein, und löst
die Gleichungen nach k auf, so erhält man die folgenden Ergebnisse:\\ \\ 
Um mit einer Wahrscheinlichkeit von mehr als 10\% eine Kollision zu erhalten benötigt man für:\\ \\
$2^{64}$ lange Bitstrings mindestens $1,9716*10^9$ Dokumente\\
$2^{128}$ lange Bitstrings mindestens $8,4679*10^{18}$ Dokumente\\
$2^{160}$ lange Bitstrings mindestens $5,5495*10^{23}$ Dokumente